package com.kabuda.hot100.栈.medium;

import java.util.ArrayList;
import java.util.Stack;

/**
 * @author kabuda
 * @date 2025-03-03 21:18
 * @description 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
 * <p>
 * 实现 MinStack 类:
 * <p>
 * MinStack() 初始化堆栈对象。
 * void push(int val) 将元素val推入堆栈。
 * void pop() 删除堆栈顶部的元素。
 * int top() 获取堆栈顶部的元素。
 * int getMin() 获取堆栈中的最小元素。
 * <p>
 * 输入：
 * ["MinStack","push","push","push","getMin","pop","top","getMin"]
 * [[],[-2],[0],[-3],[],[],[],[]]
 * <p>
 * 输出：
 * [null,null,null,null,-3,null,0,-2]
 */
public class t155_最小栈 {
    public static void main(String[] args) {
        MinStack minStack = new MinStack();
    }


    /**
     * @param
     * @author kabuda
     * @date 2025/3/3 21:35
     * @description O(1)
     */
    public static class MinStack1 {
        private Stack<Integer> stack;
        private Stack<Integer> min_stack;

        public MinStack1() {
            this.stack = new Stack<>();
            min_stack = new Stack<>();
        }

        public void push(int val) {
            stack.push(val);
            stack.push(val);
            if (min_stack.isEmpty() || val <= min_stack.peek())
                min_stack.push(val);

        }

        public void pop() {
            stack.pop();
            if (stack.pop().equals(min_stack.peek()))
                min_stack.pop();
        }

        public int top() {
            return stack.peek();
        }

        public int getMin() {
            return min_stack.peek();
        }
    }


        /**
         * @param
         * @author kabuda
         * @date 2025/3/3 21:35
         * @description O(n)
         */
        public static class MinStack {
            int min;
            ArrayList<Integer> stack;

            public MinStack() {
                min = Integer.MAX_VALUE;
                this.stack = new ArrayList<>();
            }

            public void push(int val) {
                this.min = Math.min(min, val);
                stack.add(val);
            }

            public void pop() {
                stack.remove(stack.size() - 1);
                this.min = Integer.MAX_VALUE;
                for (Integer i : stack) {
                    this.min = Math.min(min, i);
                }
            }

            public int top() {
                return stack.get(stack.size() - 1);
            }

            public int getMin() {
                return min;
            }
        }
    }
